This invention relates to high-speed image processing, specifically to an improved method for reducing the computational load of image filtering, reconstruction or interpretation.
Prior art imaging systems present images directly to the human user or store images on film. Such prior art systems are limited in capability by the physical limitations of film or by the limitations imposed by the direct viewing environment. Such prior art imaging is pervasive in its application to industrial, medical, scientific, and consumer uses and is commercially ubiquitous.
Uses for images and processed images include medical imaging, where X-rays, MRI, ultrasound, and CAT scan images are used routinely for diagnosing and treating patients. Industrial applications include inspection of components such as machined parts, or process inspection such as paper or textile manufacturing, semiconductor manufacturing, even security inspection. Images also have consumer applications. Chief among consumer applications is the capture of images on film or digitally as files for later viewing.
Modern imaging systems frequently provide facilities for storing images electronically as sampled data (pixels) that can be saved in computer memory. Such presentation provides convenient storage, flexibility for transmission, and the opportunity to improve upon the basic image data according to the task for which the image is to be used. The basic task of storing images electronically is challenging. Current image resolution, color gamut, and image size require massive storage. For example, an image may have 16 bit quantization of color coded as red, green and blue and 2048 by 2048 pixel resolution, and therefore require 24 Megabytes of memory. Storing, retrieving, processing or displaying images may exceed the the limit capability of current general purpose computers for these useful applications.
In the prior art, images that are stored electronically are processed to improve the basic image or to enhance their utilization toward a specific purpose. For example, an image can be filtered to reduce noise, edge enhanced to increase sharpness, or stretched to improve contrast, thereby making the image more visible. Images may also be interpreted by computing systems that locate and track objects or detect particular characteristics of the images or the objects within those images. Systems that process or interpret images include Data Cube Max Video, Cognex MVS 8000, and TriPath Imaging AutoPap system. These systems are generally constructed from special purpose hardware to provide custom facilities for performing image processing operations and image storage. Special purpose facilities for image processing increase system throughput capability but at significant cost and complexity. Present generation system throughput limits the complexity of the image processing operations that can be undertaken, particularly in cost sensitive applications.
Prior Art image processing system throughput is constrained by the enormity of the computational task that must be performed in typical image processing operations. An example of a task well known in the art is filtering. Prior art systems accomplish filtering through convolution, an operation which involves multiple floating point multiplications and additions in order to determine a single output value. For a 3 by 3 kernel operating on a monochrome image, determination of a single filtered image output pixel value requires 9 multiplications and 8 additions. On a large or high resolution or color image, there are millions of output values that must be so computed in order to filter the image. To overcome this difficult computational task, specialized hardware is developed. However, the specialized hardware is expensive and difficult to program. Today large kernel or three-dimensional operations are still prohibitively expensive (or slow) even with specialized hardware due to the geometric increase in the computational requirement.
The specialized hardware approach includes more than just the image processing. Every facet of the application receives special facilities. For example, prior art image processing systems usually include special facilities for video acquisition, display and storage as well as processing. Each of these special facilities requires specialized development tools. This creates a high cost of ownership and restricts application development to specialists who are familiar with the technology. Also, the custom hardware architectures that result are slow to change to incorporate technological advancements that are easily available if it were possible to borrow them from higher volume applications. For example, rapid advancements in the hardware and software technologies in personal computer (PC) are not rapidly incorporated into these special purpose systems thereby denying the benefit such advancements would bring if rapidly and automatically incorporated. As another example, recent advances in digital stream media technology are rapidly making custom hardware platforms obsolete. Datacube recently announced end of life for its Max Video 250. Prior art industrial vision systems such as these fail to capitalize on enhancements in technology targeted for the consumer applications. The result of the prior art methods is to limit the technology to high-end applications and products that can absorb the excessive cost.
It is an object of this invention to increase the speed with which image processing operations can operate on electronically stored images. A further object of the invention is to pre-compute and store as tables certain time consuming or repeated computations to reduce the time required for image processing and to remove or reduce the need for special purpose image processing hardware.
It is the object of the invention to provide very efficient and high speed image processing methods for single or multiple CPUs. Another consistent objective is to provide image processing mechanisms that utilize contemporary and ubiquitous computer architectures more efficiently to produce much higher throughput. It is a further objective to provide the improved image processing mechanisms in a manner that removes or minimizes the use of special purpose hardware designed only for an image processing task, because the invention is such that more general purpose hardware can accomplish the task with useful throughput.
According to one embodiment, the invention uses multiple CPUs wherein multiple image processing tasks are performed serially or in parallel by separate CPUs.
In another embodiment, CPU""s operate to implement heretofore multi-step functions in a single operation by use of pre-programmed look up tables.
In another embodiment, the invention includes non-linear image processing functions.
In another embodiment, the processing of image memory horizontally is accelerated by use of flat filters.
In another embodiment, the processing of image memory vertically is accomplished horizontally first then incremented vertically to increase throughput.
In still another embodiment, the processing of image memory along an off-axis direction is simplified and made faster by address offsets.
In another embodiment the processing of image memory along a circular path is simplified and made faster by address offsets.
In another embodiment, point operations are combined with kernel operations.
In another embodiment, intermediate results from look up table operations are provided.